1. Field of the Invention
The present invention relates to error correction, and more particularly to an operation apparatus with multipliers for deriving an error position polynomial .GAMMA.(x) and a Forney syndrome polynomial .GAMMA.(x) of a Galois field.
2. Description of the Prior Art,
Generally, an erasure is known in terms of position, even though unknown in terms of size, as compared with an error whose position and size are unknown. Accordingly, when information indicative of an erasure of some symbol is applied to a decoder, he erasure corresponding to two times the same number of parity errors can be corrected.
Referring to FIG. 1, here is illustrated a general erasure position power operation apparatus. The operation apparatus comprises an AND gate 1 having one input for receiving information about erasure, namely, erasure positions of binary values. To the other input of the AND gate 1, register 2 and a multiplier 3 are connected. In the AND gate 1, the erasure position is AND-combined with a value obtained through the register 2 and the multiplier 4. To an output of the AND gate 1, a non-zero detector 4 is connected, which receives an output signal from the AND gate 1 and generates a control signal C.sub.1. The control signal C.sub.1 is applied to a 2t symbol latch 5 via a switch SW.sub.a. According to the control signal C.sub.1, the 2t symbol latch 5 outputs powers for the erasure positions, namely, values .alpha..sup.j1, .alpha..sup.j2, . . . corresponding to respective erasure positions. Here, the value .alpha..sup.j1 represents the value corresponding to the first erasure position and the value .alpha..sup.j2 represents the value corresponding to the second erasure position.
Since the erasure positions are already known, they can be expressed by the following polynomial: ##EQU1## wherein, e represents the number of erasures.
FIG, 2 is a block diagram of a conventional operation apparatus utilizing the polynomial for erasure positions.
As shown in FIG. 2, the operation apparatus comprises a non-zero detector 10 for receiving an erasure position value .alpha..sup.j(i) and detecting whether the received erasure position value is zero or not, and a multi-stage operation unit including a plurality of operation circuits 20.sub.0 to 20.sub.2t-1. The operation unit comprises a plurality of adders A.sub.0 to A.sub.2t-1 and a plurality of registers R.sub.0 to R.sub.2t-1 connected with the adders A.sub.0 to A.sub.2t-1 via a plurality of switches SW.sub.0 to SW.sub.2t-1, respectively. Each of the switches SW.sub.0 to SW.sub.2t-1 are controlled by an output signal from the non-zero detector 10, to be switched on or off. According to the switching operations of the switches SW.sub.0 to SW.sub.2t-1, the registers R.sub.0 to R.sub.2t-1 store temporally output values from the adders A.sub.0 to A.sub.2t-1, respectively. The operation unit also comprises a plurality of multipliers M.sub.0 to M.sub.2t-1 each for multiplying each value stored in each corresponding one of the registers R.sub.0 to R.sub.2t-1 and each corresponding erasure position value .alpha..sup.j(i) and sending the resultant value to each corresponding one of the adders A.sub.0 to A.sub.2t-1.
In the operation apparatus with the above-mentioned construction, the register R.sub.0 is initially loaded with the value of 1, while the remaining registers R.sub.1 to R.sub.2t-1 are initially loaded with the value of 0.
When a value .alpha..sup.j(1) corresponding to the first erasure position is received in the operation apparatus, it is applied to the non-zero detector 10 and respective multipliers M.sub.0 to M.sub.2t-1 of the operation circuits 20.sub.0 to 20.sub.2t-1.
The non-zero detector 10 detects whether the received erasure position value is zero or not and outputs a detect signal, so as to control respective switches SW.sub.0 to SW.sub.2t-1 of the operation circuits 20.sub.0 to 20.sub.2t-1 . The control of each switch is carried out such that the switch is switched to its closed state when the input value of non-zero detector 10 is not zero and to its opened state when the input value is zero.
This procedure will be described in detail.
Where the first register R.sub.0 has an initial value of 1 while the remaining registers R.sub.1 to R.sub.2t-1 have initial values of 0 at a state that the input value of non-zero detector 10 is not zero; the register R.sub.0 is loaded with the first erasure position value .alpha..sup.j(1), whereas the register R.sub.1 is loaded with the value of 1. In this case, the remaining registers R.sub.2 to R.sub.2t-1 are still maintained as being loaded with the value of 0.
As the above procedure is repeated, the register R.sub.0 is sequentially loaded with values in the order of 0.fwdarw.1.fwdarw..alpha..sup.j1 .fwdarw..alpha..sup.j1 .multidot..alpha..sup.j2 .fwdarw..alpha..sup.j1 .multidot..alpha..sup.j2 .multidot..alpha..sup.j3 .fwdarw..alpha.j1.multidot..alpha..sup.j2 .alpha..sup.j3. . . The register R.sub.1 is sequentially loaded with values in the order of 0.fwdarw.1.fwdarw..alpha..sup.j1 .fwdarw..alpha..sup.1 +.alpha..sup.j2 .fwdarw.(.alpha..sup.j1+ .alpha..sup.j2).alpha..sup.j3 .fwdarw..alpha.j1.multidot..alpha..sup.j2 . . . On the other hand, the register R.sub.2 is sequentially loaded with values in the order of 0.fwdarw.0.fwdarw.1.fwdarw..alpha..sup.j1 +.alpha..sup.j2 +.alpha..sup.j3 . . . .
The sequential value storing procedures executed in the registers are shown in FIG. 3.
FIG. 5 is a block diagram of a conventional operation apparatus for deriving a Forney syndrome.
As shown in FIG. 5, the operation apparatus comprises a non-zero detector 10a for receiving an erasure position value .alpha..sup.j(i) and detecting whether the received erasure position value is zero or not, and a multi-stage operation unit including a plurality of operation circuits 20a.sub.0 to 20a.sub.2t-1. The operation unit comprises a plurality of adders A.sub.0 to A.sub.2t-1 and a plurality of registers S.sub.0 to S.sub.2t-l connected with the adders A.sub.0 to A.sub.2t-1 via a plurality of first switches SW.sub.b, respectively. Each of the first switches SW.sub.b are controlled by an output signal from the non-zero detector 10a, to be switched on or off. According to the switching operations of the first switches SW.sub.b, the registers S.sub.0 to S.sub.2t-1 store temporally output values from the adders A.sub.0 to A.sub.2t-1, respectively. The operation unit also comprises a plurality of multipliers M.sub.0 to M.sub.2t-1 each for multiplying each value loaded in each corresponding one of the registers S.sub.0 to S.sub.2t-1 and each corresponding erasure position value .alpha..sup.j(i) and sending the resultant value to each corresponding one of the adders A.sub.0 to A.sub.2t-1. The operation apparatus also comprises an output unit 30 including a plurality of registers T.sub.0 to T.sub.2t-1 each connected to each corresponding one of the registers S.sub.0 to S.sub.2t-1 via a second switch SW.sub.c.
In the operation apparatus with the above-mentioned construction, the registers S.sub.0 to S.sub.2t-1 of the operation circuits 20.sub.a0 to 20a.sub.2t-1 are initially loaded with the values of S.sub.0, S.sub.1, . . . , and S.sub.2t-1 which are coefficients of the polynomial of the syndrome, respectively.
In similar manner to the case of FIG. 2, this operation apparatus receives sequentially values .alpha..sup.k(i) corresponding to erasure positions and controls the switches SW.sub.b via the non-zero detector 10a so that the values .alpha..sup.j(i) are applied to the multipliers M.sub.0 to M.sub.2t-1, respectively.
At the first clock, thereafter, the register S.sub.0 is loaded with the value of S.sub.0, whereas the register S.sub.1 is loaded with the value of S.sub.1 +S.sub.0 .multidot..alpha..sup.j(i). On the other hand, the register S.sub.2 is loaded with the value of S.sub.2 +S.sub.1 .multidot..alpha..sup.k(1). In such a manner, the register S.sub.j is loaded with the value of S.sub.j +S.sub.j .multidot..alpha..sup.j(i).
As the above procedure is repeated according to inputting of erasure position values .alpha..sup.j(i), the registers S.sub.0 to S.sub.2t-1 are loaded with coefficients of the polynomial.
At this time, the second switches SW.sub.c are switched to its closed state by the control signal C.sub.2, so that the coefficients loaded in the registers S.sub.0 to S.sub.2t-1 are transferred to the registers T.sub.0 to T.sub.2t-1 of the output unit 30, respectively.
FIG. 4 is a circuit diagram of Galois field (GF) multipliers M.sub.0 to M.sub.2t-1 used in both the operation apparatus of FIG. 3 and the operation apparatus of FIG. 5. Each adder is an GF(2.sup.4) adder for operating one byte comprised of four bits. The GF(2.sup.4) adder comprises an AND gate and an exclusive 0R gate.
First, a source polynomial P(X) having the degree of 4 is needed for expanding GF(2) up to GF(2.sup.4).
That is, assuming the source polynomial P(X)=X.sup.4 +X+1, elements of all fields are expressed by a cubic-nomials a.sub.3 X.sup.3 +a.sub.2 X.sup.2 +a.sub.1 X+a.sub.0 =a(X). In this case, a.sub.i represents elements of GF(2).
When the cubic-nomial is expressed for .tau. and .beta. indicative of input values of each AND gate, and .THETA. indicative of one input value of each exclusive OR gate, the following cubic-nomials are obtained:
.tau.(X)=.tau..sub.3 X.sup.3 +.tau..sub.2 X.sup.2 +.tau..sub.1 X+.tau..sub.0 PA1 .beta.(X)=.beta..sub.3 X.sup.3 +.beta..sub.2 X.sup.2 +.beta..sub.1 X+.beta..sub.0 PA1 .THETA.(X)=.THETA..sub.3 X.sup.3 +.THETA..sub.2 X.sup.2 +.THETA..sub.1 X+.THETA..sub.0 PA1 .tau..sup.(1) (X)=.tau.(X) PA1 .THETA..sup.(1) (X)=.THETA.(X)+.beta..sub.0 .tau.(X) PA1 .tau..sup.(i+1) (X)=X.tau..sup.(i) (X) mod P(X) PA1 .THETA..sup.(i+1) (X)=.THETA..sup.(i) (X)+.beta..sub.i .tau..sup.(i+1) (X)
Also, .tau..multidot..beta. indicative of the output value of each AND gate is expressed by the following equation: EQU .tau..multidot..beta.=.tau.(X) .beta.(X) mod P(X)
Assuming .tau..multidot..beta.=K.sub.3 X.sup.3 +K.sub.2 X.sup.2 +K.sub.1 X+K.sub.0 the output value .tau..multidot..beta.+.THETA. of each exclusive OR gate is expressed by the following cubic-nomial: EQU .tau..multidot..beta.=(K.sub.3 +.THETA..sub.3)X.sup.3 +(K.sub.2 +.THETA..sub.2)X.sup.2 +(K.sub.1 +.THETA..sub.1)X+(K.sub.0 +.THETA..sub.0)=W.sub.3 X.sup.3 +W.sub.2 X.sup.2 +W.sub.1 X+W.sub.0
The operation of the first row is carried out as follows:
The operation of the i-th row is carried out as follows:
Each cell performs the following two functions: EQU .tau..sub.j.sup.(i+1)=.tau..sub.j.sup.(i)+.tau..sub.3.sup.(i) P.sub.j EQU .THETA..sub.j.sup.(i+1)=.THETA..sub.j-1.sup.(i) +.beta..sub.i .tau..sub.j.sup.(i+1)
wherein, .THETA..sub.j.sup.(i+1) represents the i-th row .multidot.j-th column.
For example, in the first cell of the second row, .tau..sub.3 and .beta..sub.1 are ANDed in the AND gate AD.sub.2.1 and then exclusively ORed in the exclusive OR gate XOR.sub.2.1, so as to be outputted as .THETA..sub.0.sup.(2). In the second cell, .tau..sub.3.sup.(0) and .tau..sub.0 are exclusively ORed in the exclusive OR gate XOR.sub.2.2, so as to be provided as one input of AND gate AD.sub.2.3.
The output from the exclusive OR gate XOR.sub.2.2 is ANDed with .beta..sub.1 in the AND gate AD.sub.2.3 and then exclusively ORed in the exclusive OR gate XOR.sub.2.3, so as to be outputted as .THETA..sub.1.sup.(1). In such a manner, the operation is repeated up to the final row.
As a result, the following results are obtained: EQU .THETA..sub.0.sup.(4) =W.sub.0 .sup.(4) =W.sub.1, .THETA..sub.2.sup.(4) =.THETA..sub.2, .THETA..sub.3.sup.(4) =W.sub.3.
In the conventional circuit, however, the content of registers based on the polynomial for erasure positions includes the initial value of 1 only for the register R.sub.0 and the initial value of 0 for the remaining registers R.sub.1 to R.sub.2t-1.
For each input .alpha..sup.j(i) only one of such registers is used while the remaining registers are unnecessary. Accordingly, the multipliers for deriving values for the remaining registers are also unnecessary.
That is, for the operation of the polynomial for erasure positions, 2t GF multipliers and 2t adders are needed. In GF multipliers, the larger the symbol field, the more the number of exclusive OR gates.
As a result, where a Reed Solomon decoder is realized by using very large size integrated circuit chips, the area occupied by the multipliers is increased due to the increased number of exclusive OR gates. Furthermore, when symbol fields of codes are very large and the erasure correction capacity is large, the chip area becomes relatively large. The flow of signals is also vague, so that a correct operation can not be carried out.